LeetCode 51.N-Queens

51.N-Queens(N皇后)

链接

https://leetcode-cn.com/problems/n-queens/

题目

n _皇后问题研究的是如何将 _n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给定一个整数 n ，返回所有不同的 _n _皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例:

　　输入: 4
　　输出: [
　　 [".Q..",  // 解法 1
　　  "...Q",
　　  "Q...",
　　  "..Q."],

　　 ["..Q.",  // 解法 2
　　  "Q...",
　　  "...Q",
 　　 ".Q.."]
　　]
　　解释: 4 皇后问题存在两个不同的解法。

思路

这题的思路和之前的N皇后II一样，都是运用回溯法，只是输出较难设置，还有一个重点，是其中存放答案的res，需要在每次计算前clear一下，要不然就无法ac。

代码

private static boolean col[];
private static boolean line1[];
private static boolean line2[];
private static int answer[];
private static List<List<String>> res = new LinkedList<>();

public static List<List<String>> solveNQueens(int n) {
  col = new boolean[n];
  line1 = new boolean[2 * n - 1];
  line2 = new boolean[2 * n - 1];
  answer = new int[n];
  res.clear();
  putQueen(n, 0);
  return res;
}

private static void putQueen(int n, int index) {
  if (index == n) {
    List<String> item = new ArrayList<String>();
    for (int i = 0; i < answer.length; i++) {
      StringBuilder sb = new StringBuilder();
      for (int j = 0; j < answer.length; j++) {
        if (answer[i] != j) {
          sb.append('.');
        } else {
          sb.append('Q');
        }
      }
      item.add(sb.toString());
    }
    res.add(item);
  }

  for (int i = 0; i < n; i++) {
    if (!col[i] && !line1[i - index + n - 1] && !line2[i + index]) {
      answer[index] = i;
      col[i] = true;
      line1[i - index + n - 1] = true;
      line2[i + index] = true;

      col[i] = false;
      line1[i - index + n - 1] = false;
      line2[i + index] = false;
    }
  }
}